//题目:
// 在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。
// 行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
// 象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
// 每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
// 骑士继续移动，直到它走了 k 步或离开了棋盘。

// 返回 骑士在棋盘停止移动后仍留在棋盘上的概率 。

// 示例 1：
// 输入: n = 3, k = 2, row = 0, column = 0
// 输出: 0.0625
// 解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
// 在每一个位置上，也有两种移动可以让骑士留在棋盘上。
// 骑士留在棋盘上的总概率是0.0625。

// 示例 2：
// 输入: n = 1, k = 0, row = 0, column = 0
// 输出: 1.00000
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
    int dx[8]={-1,-2,-2,-1,1,2,2,1},dy[8]={-2,-1,1,2,2,1,-1,-2};
public:
    double knightProbability(int n, int count, int row, int col) 
    {
        //1.创建dp表————dp[k][i][j]表示：走k步来到(i,j)位置的概率
        vector<vector<vector<double>>> dp(count+1,vector<vector<double>>(n,vector<double>(n)));
        //2.初始化
        dp[0][row][col]=1;
        //3.填表
        double ret=0;
        for(int k=1;k<=count;k++)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    //计算走k步，能来到(i,j)位置的概率
                    for(int pos=0;pos<8;pos++)
                    {
                        int x=i+dx[pos],y=j+dy[pos];
                        if(x>=0 && x<n && y>=0 && y<n && dp[k-1][x][y]!=0)
                            dp[k][i][j]+=dp[k-1][x][y]/8;
                    }
                    if(k==count) ret+=dp[k][i][j];
                }
            }
        }
        //4.确定返回值
        return count==0?1:ret;
    }
};

 